Міністерство освіти України Національний університет «Львівська політехніка» Кафедра автоматизованих систем управління
МЕТОДИЧНІ ВКАЗІВКИ З практичних робіт з дисципліни "Моделювання систем" для студентів базового напрямку 6.050101 “Комп’ютерні науки” Львів 2011  Імітаційне моделювання процесу функціонування скінченого дискретного стохастиного автомата. Методичні вказівки до лабораторної роботи з дисципліни “Моделювання систем” для студентів базового напрямку 6.050101 “Комп’ютерні науки”/ Укладач: к.т.н., доцент кафедри АСУ Кузьмін О.В. – Львів, Національний університет “Львівська політехніка”, 9 с. Укладач: Кузьмін Олександр Васильович Відповідальний за випуск: к.т.н., доцент Шпак З.Я. Рецензент: д.т.н., професор Різник В.В. Методичні вказівки затверджено на засіданні кафедри АСУ Протокол № 2-2011/2012 від 20 вересня 2011 р. ПРАКТИЧНЕ ЗАНЯТТЯ 2. ДИСКРЕТНО-ДЕТЕРМІНОВАНІ МОДЕЛІ (F-СХЕМИ). Особливості дискретно-детермінованого підходу розглянемо на прикладі використання в якості математичного апарату теорію автоматів. На основі цієї теорії система представляється у вигляді автомата, який перетворює дискретну інформацію і змінює свій внутрішній стан лише в допустимі моменти часу. Абстрактний скінчений автомат можна представити як математичну схему, яка характеризується шістьма елементами: скінченою множиною х вхідних сигналів (вхідний алфавіт), скінченою множиною y вихідних сигналів (вихідний алфавіт), скінченою множиною z внутрішніх станів (внутрішній алфавіт), початковим станом z0, функцією переходів
(z,x), функцією виходів
(z,x). Автомат задається: F(z, x, y,
,
, z0). (4.1) Цей автомат функціонує в дискретному автоматному часі, моментами якого є такти, кожному з яких відповідають постійні значення вхідних, вихідних сигналів і внутрішній стан. Робота скінченого автомата виконується по наступній схемі: в кожному t+1 такті на вхід автомата, який знаходиться в стані z(t), подається деякий сигнал x(t+1), на який він реагує переходом в t+1 такті в новий стан z(t+1) з видачею деякого вихідного сигнала. Для F-автомата першого роду, який називається автоматом Мілі, можна записати такі співвідношення: z(t+1)=
[z(t), x(t+1)], t=0,1,2, ... (4.2) y(t+1)=
[z(t), x(t+1)], t=0,1,2, ... (4.3) Скінчений автомат другого роду можна представити: z(t+1)=
[z(t), x(t+1)], t=0,1,2, ... (4.4) y(t+1)=
[z(t+1), x(t+1)], t=0,1,2, ... (4.5) Якщо y(t)=
[z(t)] , то такий автомат другого роду називається автоматом Мура. По кількості станів розрізняють скінчені автомати з пам’ятю і без пам’яті. Автомати з пам’ятю мають більше одного стану, а автомати без пам'яті (комбінаційні, логічні схеми) мають лише один стан. Робота комбінаційної схеми згідно (4.6) заключається в тому, що вона ставить у відповідність кожному вхідному сигналу x(t) певний вихідний сигнал Y(t), тобто реалізує логічну функцію виду: y(t)=
[x(t)], t=0,1,2, ... (4.6) Ця функція називається булевою, якщо алфовіти x та y складаються з двох літер. По характеру відліку дискретного часу скінчені автомати поділяються на синхронні і асинхронні. В синхронних F- автоматах моменти часу, в які автомат зчитує вхідні сигнали визначаються примусово синхронізуючими сигналами. Після чергового синхронізуючого сигнала з врахуванням зчитаного і у відповідності з рівняннями (4.2)-(4.5) відбувається перехід в новий стан і видача сигнала на виході, після чого автомат може сприймати наступне значення вхідного сигналу. Асинхронний F-автомат зчитує вхідний сигнал неперервно і тому, реагуючи на достатньо довгий вхідний сигнал постійної величини x він може, як випливає з рівнянь (4.2)-(4.5), декілька разів змінювати свій стан видаючи відповідну кількість вихідних сигналів, поки не перейде в стійкий, який вже не може бути змінений даним вхідним сигналом. Існує декілька способів задання роботи F- автоматів, але найчастіше використовується табличний, графічний та матричний. Найпростіший - табличний спосіб задання скінченого автомата, який базується на використа...